package com.hdu.other.tanxin;

public class lc132 {
    class Solution {
        public int cuttingBamboo(int n) {
             if (n <= 2)
             {
                 return 1;
             }
             if (n == 3)
             {
                 return 2;
             }
             int tail = (n % 3 == 0 ? 1 : (n % 3 == 1 ? 4 : 2));
             int pow = (tail == 1 ? n : (n - tail)) / 3;
             return (int) (pow(3, pow, 1000000007) *tail % 1000000007);
        }

        long pow(long x, int n, int mod)
        {
            long ans = 1;
            while (n > 0) {
                if (n % 2 == 1) {
                    ans = (ans * x) % mod;
                }
                x = (x * x) % mod;
                n /= 2;
            }
            return ans;
        }
    }
}
